package com.practice.dataStructure.Heap;

import java.util.ArrayList;
import java.util.NoSuchElementException;

/**
 * 堆中的每一个节点值都大于等于（或小于等于）子树中所有节点的值。或者说，任意一个节点的值都大于等于（或小于等于）所有子节点的值。
 * 使用场景：多次获取最大值或者最小值，且进行频繁的插入和删除
 * 最大堆：堆中的每一个节点的值都大于等于子树中所有节点的值
 * 最小堆：堆中的每一个节点的值都小于等于子树中所有节点的值
 */
public class Heap {
    //使用树形数组进行存储
    private ArrayList<Integer> heap;

    //从零开始，父节点为i，则左节点为2i+1，右节点为2i+2
    public Heap(){
        heap = new ArrayList<>();
    }

    public Heap(int capacity){
        heap = new ArrayList<>(capacity);
    }

    public void insert(int value){
        //直接插入末尾
        heap.add(value);
        //自底向上调整堆
        heapifyUp(heap.size()-1);
    }

    //堆中移除并返回堆顶元素
    public int removeMax(){
        if(heap.isEmpty()){
            throw new NoSuchElementException("Heap is empty");
        }
        int max = heap.get(0);
        int lastElement = heap.remove(heap.size()-1);
        if(!heap.isEmpty()){
            heap.set(0,lastElement);
            //自顶向下调整堆
            heapifyDown(0);
        }
        return max;
    }

    //获取堆顶元素
    public int getMax(){
        if(heap.isEmpty()){
            throw new NoSuchElementException("Heap is empty");
        }
        return heap.get(0);
    }

    //检查堆是否为空
    public boolean isEmpty(){
        return heap.isEmpty();
    }

    //堆化向上调整
    private void heapifyUp(int index){
        while (index > 0 ){
            int parentIndex = (index-1)/2;
            if(heap.get(index)>heap.get(parentIndex)){
                swap(index,parentIndex);
                index = parentIndex;
            }else{
                break;
            }
        }
    }

    //堆化向下调整
    private void heapifyDown(int index){
        while (true){
            int leftChildIndex = 2*index+1;
            int rightChildIndex = 2*index+2;
            int largestIndex = index;

            if(leftChildIndex < heap.size() && heap.get(leftChildIndex)>heap.get(largestIndex)){
                largestIndex = leftChildIndex;
            }
            if(rightChildIndex<heap.size() && heap.get(rightChildIndex) > heap.get(largestIndex)){
                largestIndex = rightChildIndex;
            }

            if(largestIndex != index){
                swap(index,largestIndex);
                index = largestIndex;
            }else {
                break;
            }
        }
    }

    //交换堆中的两个元素
    private void swap(int i,int j){
        int temp = heap.get(i);
        heap.set(i,heap.get(j));
        heap.set(j,temp);
    }
}
